/**
 *  * Definition for singly-linked list.
 *
 *        */
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <set>
#include <string.h>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
    public:
        ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
            if(l1 == NULL)
                return l2;
            if(l2 == NULL)
            return l1;
            ListNode* list = NULL;
            auto head = list;
            auto it1 = l1;
            auto it2 = l2;
            bool add = false;
            while(1)
            {
                int num = 0;
                if(add)
                {
                    num += 1;
                    add = false;
                }
                if(it1 == NULL &&  it2 == NULL && num == 0)
                    break;
                if(it1 != NULL)
                    num += it1->val;
                if(it2 != NULL)
                    num += it2->val;
                if(num >= 10)
                    add = true;
                if(list == NULL)
                {
                    list = new ListNode(num%10);
                    head = list;
                }
                else
                {
                    auto node = new ListNode(num%10);
                    list->next = node;
                    list = node;
                }
                if(it1 != NULL)
                    it1 = it1->next;
                if(it2 != NULL)
                    it2 = it2->next;
            }
            return head;
        }
        int lengthOfLongestSubstring(string s) {
            int maxSize = 0;
            string sub;
            for(int i = 0; i < s.size();i++)
            {
                auto position = sub.find(s[i]);
                if( position != sub.npos  )
                {
                    if(sub.size() > maxSize)
                        maxSize = sub.size() ;
                    sub = sub.substr(position+1);
                }
                sub += s[i];
            }
            return maxSize;
        }

        static string convert(string s, int numRows) {
            int  w = (s.size() /(2 * numRows - 2)) * (numRows -1) + (s.size() % (2 * numRows - 2))/numRows +  (s.size() % (2 * numRows - 2)) %numRows;
            char nsp[w][numRows];
            memset(nsp,0, sizeof(nsp));
            int index = 0;
            int row = 0;
            bool upordown = true;
            for (int i = 0; i < s.size(); ++i) {
                if(row == numRows-1)
                    upordown = false;
                if(row == 0)
                    upordown = true;
                nsp[index][row] = s[i];
                if(upordown)
                    row++;
                else
                {
                    index++;
                    row--;
                }
            }
            string str;
            for (int i = 0; i < numRows; i ++)
            {
                for (int j = 0; j < w ; ++j) {
                    if (nsp[j][i] == 0)
                    {
                        cout<<"  ";
                    }
                    else
                    {
                        cout<<nsp[j][i]<<" ";
                        str += nsp[j][i];
                    }
                }
                cout<<endl;
            }
            return str;
        }
};

void trimLeftTrailingSpaces(string &input) {
    input.erase(input.begin(), find_if(input.begin(), input.end(), [](int ch) {
        return !isspace(ch);
    }));
}

void trimRightTrailingSpaces(string &input) {
    input.erase(find_if(input.rbegin(), input.rend(), [](int ch) {
        return !isspace(ch);
    }).base(), input.end());
}

vector<int> stringToIntegerVector(string input) {
    vector<int> output;
    trimLeftTrailingSpaces(input);
    trimRightTrailingSpaces(input);
    input = input.substr(1, input.length() - 2);
    stringstream ss;
    ss.str(input);
    string item;
    char delim = ',';
    while (getline(ss, item, delim)) {
        output.push_back(stoi(item));
    }
    return output;
}

ListNode* stringToListNode(string input) {
    // Generate list from the input
    vector<int> list = stringToIntegerVector(input);

    // Now convert that list into linked list
    ListNode* dummyRoot = new ListNode(0);
    ListNode* ptr = dummyRoot;
    for(int item : list) {
        ptr->next = new ListNode(item);
        ptr = ptr->next;
    }
    ptr = dummyRoot->next;
    delete dummyRoot;
    return ptr;
}

string listNodeToString(ListNode* node) {
    if (node == nullptr) {
        return "[]";
    }

    string result;
    while (node) {
        result += to_string(node->val) + ", ";
        node = node->next;
    }
    return "[" + result.substr(0, result.length() - 2) + "]";
}

int main() {
    ListNode* l1 = stringToListNode("[5]");
    ListNode* l2 = stringToListNode("[5]");

    ListNode* ret = Solution().addTwoNumbers(l1, l2);

    string out = listNodeToString(ret);
    cout << out << endl;
    int len = Solution().lengthOfLongestSubstring("dvdf");
    cout<<len<<endl;
    cout<<"z:"<<Solution::convert("LEETCODEISHIRING",3)<<endl;;
    return 0;
}
